package com.example.leetdemo.process;

public class Solution440 {
    NumberNode root = new NumberNode();
    public int findKthNumber(int n, int k) {
        initNumberTree(n);
        NumberNode numberNode = preorderSearch(k);
        StringBuilder stringBuilder = new StringBuilder();
        while (numberNode != root) {
            stringBuilder.append(numberNode.num);
            numberNode = numberNode.father;
        }
        stringBuilder.reverse();
        System.err.println("init success");
        return Integer.parseInt(stringBuilder.toString());
    }

    private void initNumberTree(Integer n) {
        root.count = 0;
        for (int i = 1; i <= n; i++) {
            String p = i + "";
            NumberNode temp = root;
            for (int j = 1; j <= p.length(); j++) {
                int q = p.charAt(j - 1) - '0';
                if (temp.numberNodes[q] == null) {
                    temp.numberNodes[q] = new NumberNode();
                    temp.numberNodes[q].father = temp;
                    temp.numberNodes[q].num = q;
                }
                temp.numberNodes[q].count++;
                temp.count++;
                temp = temp.numberNodes[q];
            }
        }
    }

    private NumberNode preorderSearch(Integer k) {
        NumberNode p = root;
        int count = 0;
        for (int i = 1; i < 10; i++) {
            if (k <= count + p.numberNodes[i].count) {
                return preorder(p.numberNodes[i], k, count);
            } else {
                count += p.numberNodes[i].count;
            }
        }
        return root;
    }

    private NumberNode preorder(NumberNode numberNode, int num, int preCount) {
        if (preCount + 1 == num) {
            return numberNode;
        }
        preCount++;
        NumberNode p = numberNode;
        for (int i = 0; i < 10; i++) {
            if (p.numberNodes[i] == null) {
                continue;
            }
            if (num <= preCount + p.numberNodes[i].count) {
                return preorder(p.numberNodes[i], num, preCount);
            } else {
                preCount += p.numberNodes[i].count;
            }
        }
        return numberNode;
    }

    public class NumberNode {
        NumberNode father;
        Integer num;
        Integer count = 0;
        NumberNode[] numberNodes = new NumberNode[10];
    }

    public static void main(String[] args) {
        String a = 1 + "";
        System.err.println(a.length());
//        System.err.println((int)a.charAt(0));
        Solution440 solution440 = new Solution440();
        System.err.println(solution440.findKthNumber(10, 3));
    }
}
